In proposed or constructed, highly parallel multiprocessor systems, it is often the case that access to a shared memory is provided by means of a message or packet switched, multi-stage network. In such networks, contention for memory access can create serious bottlenecks. Characteristically, such communication systems do not provide each processor with a direct, dedicated connection to every memory location. It is often necessary for the data in a memory location to be moved over several communication links before it can be delivered to the processor that has requested it. Furthermore, such communication links are, in general, required to operate concurrently. There are three hurdles that must be overcome in such an interconnection network; memory bottlenecks, message traffic bottlenecks and "hot spots".
Memory bottlenecks arise because even though each memory consists of a number of locations, it is often possible to retrieve only one location during each step. If several processors simultaneously need to access different locations stored in a single memory, or memory module, those accesses can only be accomplished sequentially.
Traffic bottlenecks arise because each communication link in the system can transmit only one message at any instant. If several processors need to fetch data over a single link, they can only be transmitted sequentially.
Hot spots arise when a large number of processors need to access concurrently the same memory location within a memory module. Those accesses must not all be allowed to reach the memory module simultaneously because the memory can only service one request at each step.
An interconnection network must provide integrated solutions to these problems. Three of the more promising efforts in this area have been the NYU Ultra Computer, IBM's RP3 and Columbia University's GEM System. Each of these systems propose the use of techniques of "message combining" within the interconnection switch to use its multi-stage nature to help alleviate potential memory access bottlenecks. The NYU Ultra Computer System is described in "The NYU Ultra Computer--Designing a MIMD, Shared Memory Parallel Machine", by Gottlieb et al., IEEE Transactions on Computers, February 1983, pages 175-189. The IBM machine is described in "The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture", Proceedings of International Conference on Parallel Processing, (1985) pages 764-771. The Columbia machine is described by Sullivan et al. in "a Large Scale Homogeneous, Fully Distributed Parallel Machine" Proceedings of the Fourth Annual Syxposium on Computer Architecture, 1977, at pages 105-124.
Message combining works by detecting the occurrence of memory request messages directed at identical memory locations as they pass through each switch node in the interconnection network. Such messages are then combined, at the switch node, into a single message. The fact that such a combination took place is recorded in a buffer memory resident in each switch node. When the reply to a combined message reaches a node where it was combined, multi replies are generated to satisfy the multi individual requests. This is the message combining protocol described for the NYU Ultra Computer. The IBM scheme is similar while the Columbia/GEM scheme operates somewhat differently, acting more like a cache at each network node. Those systems involve rather complex designs.
Message combining often requires that each node maintain a table which remembers which messages have gone through the node. Additionally, when a message arrives, its destination is compared with all messages which are waiting at the node and identical destination messages are combined. These comparisons take considerable time and require expensive equipment to accomplish the comparison rapidly. Furthermore, it is still possible to miss combinations if messages directed at the same location do not arrive at the same node at the same time. Finally, the reply path distribution is complex (e.g., data returns to requesting processors); involves the use of a table/comparison protocol and extensive and time consuming use of associative memories.
Other solutions have been suggested to solve the hot-spot memory access problem which do not involve the interconnection network. For instance, hot-spots can be avoided if a copy of data to be accessed by a plurality of processors is duplicated in a number of memories. However, this approach requires substantial overhead in deciding which copy of the data is to be read (of the several copies possible) and updating the copies is complex.
Accordingly, it is an object of this invention to provide an optimum interconnection network in a multi processor/memory system.
It is a further object of this invention to provide a node-based interconnection network in a multi processor/memory system which employs message combining but with a minimum of added equipment.
It is still a further object of this invention to provide a node-based, multi processor/memory system interconnection network which provides simple reverse path routing.